package demo;


import java.util.List;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User:34398
 * Date:2024-03-30
 * Time:16:52
 */


class MyList<T extends Comparable<T>> implements IListOpera<T> {


    //静态内部类
    static class ListNode<T> {
        public T val;//值
        public ListNode next;//指针,直接默认null

        public ListNode(T val) {
            this.val = val;
        }

    }

    private ListNode<T> head;

    private void checkIndex(int Index) {
        if (Index < 0 || Index > size()) {//一越界了
            throw new IndexNOlegalException("要插入的下标越界了");
        }
    }


    @Override
    public void display() {
        ListNode<T> head = this.head;
        if (head == null) {
            return;
        } else {

            ListNode<T> cur = head;
            while (cur != null) {
                System.out.println(cur.val);
                cur = cur.next;
            }
            System.out.println();
        }
    }

    @Override
    public void display(ListNode<T> newNode) {
        if (newNode == null) return;
        ListNode<T> cur = newNode;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
        System.out.println();
    }


    @Override
    public int size() {
        if (this.head == null) {
            return 0;
        }
        ListNode<T> cur = this.head;
        int count = 0;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    @Override
    public void addFirst(T val) {

        //空链表方式是一样的
        ListNode<T> newNode = new ListNode<>(val);//创建并初始化节点
        newNode.next = this.head;//新的节点的下一个指向头
        this.head = newNode;//头变成新的节点的指针
    }

    @Override
    public void addLast(T val) {

        ListNode<T> newNode = new ListNode<>(val);

        newNode.next = null;//记住这个尾巴一定要置为空
        if (this.head == null) {
            //链表为空，直接插入返回
            this.head = newNode;
            return;
        }

        //遍历链表，到最后一个
        ListNode<T> end = this.head;
        while (end.next != null) {
            end = end.next;
        }
        end.next = newNode;
    }


    @Override
    public void addIndex(int index, T val) {

        //检查下标是否越界
        try {
            this.checkIndex(index);//抛出异常
        } catch (IndexNOlegalException e) {
            e.printStackTrace();//打印出错的信息
        }


        //找到这个下标
        int count = 0;
        ListNode<T> cur = this.head;
        ListNode<T> pre = this.head;
        while (count != index) {
            pre = cur;
            cur = cur.next;
            count++;
        }
        if (index == 0) {
            this.addFirst(val);
            return;
        } else if (index == this.size()) {
            this.addLast(val);
            return;
        } else {
            ListNode<T> newNode = new ListNode<>(val);
            pre.next = newNode;
            newNode.next = cur;
        }

    }

    @Override
    public ListNode<T> findIndexSubOne(int index) {
        int count = 0;
        ListNode<T> cur = this.head;
        while (count != index) {
            count++;
            cur = cur.next;
        }
        return cur;
    }

    @Override
    public boolean contains(T val) {
        ListNode<T> cur = this.head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
        }
        return false;
    }


    private ListNode<T> findVal(T val) {//找到含有第一个==val的引用，然后返回引用，如果没有返回空
        ListNode<T> cur = this.head;
        while (cur != null) {

            if (cur.val == val) return cur;
            cur = cur.next;
        }
        return null;//如果链表为空，直接自动返回空
    }

    @Override
    public void remove(T val) {

        if (this.head == null) {
            return;
        }
        if (this.head.val == val) {
            ListNode<T> tmp = this.head;

            this.head = this.head.next;
            tmp = null;
            return;
        }

        ListNode<T> is = this.findVal(val);
        if (is == null) {
            System.out.println("没有找到此元素，无法删除！");
            return;
        } else {//一定找的到这个元素
            ListNode<T> cur = this.head;

            while (cur.next != null) {
                if (cur.next.val == val) {
                    ListNode<T> del = cur.next;
                    cur.next = del.next;
                    del = null;
                    return;
                }
                cur = cur.next;
            }
        }

    }

    @Override
    public void removeAllKey(T val) {
        if (this.head == null) return;


        ListNode<T> prev = head;
        ListNode<T> cur = head.next;
        while (cur != null) {
            if (cur.val == val) {//当前值要删除

                ListNode<T> del = cur;
                cur = del.next;
                prev.next = cur;
                del = null;

            } else {//当前值不删除
                prev = cur;
                cur = cur.next;
            }
        }

        //还要判断头结点的元素是否需要删除
        if (this.head.val == val) {
            ListNode<T> del = this.head;
            this.head = this.head.next;
            del = null;
        }
        return;
    }

    @Override
    public void clear() {
        if (this.head == null) return;
        ListNode<T> cur = this.head;
        ListNode<T> del = null;
        while (cur != null) {
            del = cur;
            cur = cur.next;
            del = null;
        }
        this.head = null;
    }

    @Override
    public ListNode<T> reverseList() {//返回新的头结点

        if (this.head == null || this.head.next == null) return this.head;
        ListNode<T> prev = this.head;
        ListNode<T> cur = this.head.next;
        ListNode<T> tmp = null;

        prev.next = null;
        while (cur.next != null) {
            tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }

        cur.next = prev;//cur已经是最后一个不为空的节点了，把他的next改成上一个节点的引用
        this.head = cur;//头结点更新
        return this.head;
    }

    @Override
    public ListNode<T> middleNode() {
        ListNode<T> slow = this.head;
        ListNode<T> fast = this.head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;//走两步
            slow = slow.next;
        }
        return slow;
    }

    @Override
    public T kthToLast(int k) {//要判断k是否合法

        try {
            if (k == 0) checkIndex(-1);
            else checkIndex(k);
        } catch (IndexNOlegalException e) {
            e.printStackTrace();
            System.out.println("K不合法");
        }

        //用快慢指针去找
        ListNode<T> fast = this.head;
        ListNode<T> slow = this.head;

        int count = 0;
        while (count < k - 1) {        //先让快指针去走k-1步

            count++;
            fast = fast.next;
        }
        while (fast.next != null) {        //然后在一起走，直到快指针到达了最后一个节点

            fast = fast.next;
            slow = slow.next;
        }


        return slow.val;//然后slow.val就是要寻找的倒数值
    }

/*    private void addLastPart(ListNode<T> cur, ListNode<T> head) {//把cur节点，尾插到head链表中
    //   cur=null;//////////////////////////////////////////////////////////

        if (head == null) {
            //链表为空，直接插入返回
            head = cur;
            return;
        }

        //遍历链表，到最后一个
        ListNode<T> end = head;//优先访问自己的head
        while (end.next != null) {
            end = end.next;
        }
        end.next = cur;


    }*/

    @Override
    public ListNode<T> partition(T x) {

        //定义指针  用来管理x左右区间的链表
        //左边小于x 右边大于等于x
        ListNode<T> aHead = null;
        ListNode<T> aEnd = null;
        ListNode<T> bHead = null;

        ListNode<T> bEnd = null;
        ListNode<T> cur = this.head;//cur用于遍历原来的链表


        while (cur != null) {//这个循环用于，生成a b链表
            //所有数据都是头插
            if (cur.val.compareTo(x) < 0) {//小于零，放在a中
                //把cur节点尾插，到a
//                addLastPart(cur, aHead);
                while (true) {
                    if (aHead == null) {
                        //链表为空，直接插入返回
                        aHead = cur;
                    } else {//找到a链表的最后一个节点,把cur尾插到aEnd
                        aEnd.next = cur;
                    }
                    break;
                }
                aEnd = cur;//尾节标记点，等一下链接a b用
                cur = cur.next;//去判断下一个节点

            } else {//大于等于零，放到b中
                //把cur节点尾插，到b
//                    addLastPart(cur, bHead);
                while (true) {
                    if (bHead == null) {
                        //链表为空，直接插入返回
                        bHead = cur;
                    } else {
                        bEnd.next = cur;//尾插到bEnd
                    }
                    break;
                }
                bEnd = cur;//更行尾节点，等一下链接a b用

                cur = cur.next;//去判断下一个节点
            }
        }//这个循环结束之后，会得到，a 和 b的尾节点 aEnd bEnd


        //在b链表中，查看收否有x，
        //有，把他头插，到b
        //没有就不管
        while (true) {

            if (bHead == null || bHead.next == null) break;//只有一个节点，或者没有节点，就不用了
            ListNode<T> bCur = bHead.next;
            ListNode<T> bprev = bHead;

            bEnd.next = null;//记得把b的尾节点的下一个节点null

            while (bCur != null) {//把所有等于x的头插

                if(bCur.val==x){//相等把他取出来，头插到bHead
                    ListNode<T> tmp=bCur;
                    bprev.next=bCur.next;//跳出来
                    tmp.next=bHead;
                    bHead=tmp;
                    bCur=bprev.next;
                    continue;
                }

                bCur=bCur.next;
                bprev=bprev.next;
            }
            break;
        }

        if(aEnd!=null) {//左边有节点
            aEnd.next = bHead;//链接尾节点
            this.head = aHead;
        }else{
            this.head=bHead;
        }


        return this.head;
    }
}

public class Main {

    public static void main(String[] args) {
        MyList<Integer> myList = new MyList<>();

        myList.addLast(7);
//        myList.addLast(9);
//        myList.addLast(5);
//        myList.addLast(5);
//        myList.addLast(8);
//        myList.addLast(10);
//        myList.addLast(2);
//        myList.reverseList();
        System.out.println("==========");
        myList.partition(1);
        myList.display();
    }
}

